package Lee_code;

import java.util.ArrayList;
import java.util.List;

/**
 * @author blh
 * @date 2024年07月20日 8:26
 */
public class Lee_207_720 {
    List<List<Integer>> edges;
    int[] visited;
    boolean valid = true;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 需要运用图的思想
        edges = new ArrayList<>();
        // 初始化各个边
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<Integer>());
        }
        // 创建visited表
        visited = new int[numCourses];
        // 初始化图
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
        }
        // 如果有环就返回false
        for (int i = 0; i < numCourses && valid; i++) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return valid;
    }
    // visited[v] == 0 未搜索
    // visited[v] == 1 搜索中
    // visited[v] == 2 搜索完成
    // 如果搜索中的节点再次被搜索到, 说明图中有环, 失败
    private void dfs(int u) {
        visited[u] = 1;
        for (int v : edges.get(u)) {
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }
}
